﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
/*
==================================================================================================
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/product-of-array-except-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
==================================================================================================
*/




int* productExceptSelf(int* nums, int numsSize, int* returnSize) 
{
	*returnSize = numsSize;
	int* ans=(int*)malloc(numsSize * sizeof(int));
	int* left = (int*)malloc(numsSize * sizeof(int));
	int* right = (int*)malloc(numsSize * sizeof(int));
	left[0] = 1;
	right[numsSize - 1] = 1;
	for (int i = 1; i < numsSize; i++)
	{
		left[i] = left[i - 1] * nums[i - 1];
	}
	for (int i = numsSize - 2; i >= 0; i--)
	{
		right[i] = right[i + 1] * nums[i + 1];
	}
	for (int i = 0; i < numsSize; i++)
	{
		ans[i] = right[i] * left[i];
	}
	return ans;
}